<!DOCTYPE html>
<html>
    <head>
        <meta name="viewport" content="initial-scale=1.0, user-scalable=no" />
        <script type="text/javascript" src="http://maps.google.com/maps/api/js?sensor=false"></script>
        <script type="text/javascript">
            //<![CDATA[

HTMLElement.prototype.hide = function() {
    if (this.className.search("hidden") < 0) {
	    this.className = this.className.concat(" hidden");
	}
}

HTMLElement.prototype.show = function() {
	if (this.className.search("hidden") >= 0) {
	    this.className = this.className.replace("hidden", "");
	}   
}

HTMLElement.prototype.press = function() {
    if (this.className.search("current") < 0) {
	    this.className = this.className.concat(" current");
	}
}

HTMLElement.prototype.depress = function() {
	if (this.className.search("current") >= 0) {
	    this.className = this.className.replace("current", "");
	}
}


var tgd = tgd || {};
tgd.Tools = tgd.Tools || {};

tgd.Tools.MapGraph = function (canvas, callback) {

    var _minimumSpanningPolys = [];
    var _convexHullPolys = [];
    var _edgePolys = [];
    var _shortestPathPoly = null;
    var _currentSolution;
    var _output = { Tests : [] };
    var _solutions = [];
    var _vertices = [];
    var _edges = [];
    var _markers = [];
    var _shortestPathFrom;
    var _shortestPathTo;
    var _shortestPathCurrent = null;
    var _shortestPathRunnning = false;
    var _shortestPathRate = 1024;
    var _onNewShortestPath = callback;
    var _map = new google.maps.Map (
        canvas,
        {
            zoom: 5,
            center: new google.maps.LatLng(40.76883724449149, -98.51493554687498),
            mapTypeId: google.maps.MapTypeId.ROADMAP,
            disableDefaultUI : true
        }
    );

    this.__defineGetter__("Output", function() { return JSON.stringify(_output); });
    this.__defineGetter__("Markers", function() { return _markers; });
    this.__defineGetter__("Map", function() { return _map; });
    this.__defineGetter__("NumShortestPaths", function() { return _currentSolution.ShortestPaths.length; });
    this.__defineGetter__("ShortestPathRate", function() { return _shortestPathRate; });

    this._paintPolyline2 = function(options) {
        var poly;

        poly = new google.maps.Polyline(options);

        return poly;
    }

    this._paintPolyline = function(a, b, c) {
        var poly;
        if (c === undefined) {
            c = { strokeColor : "#000000", strokeOpacity : 1.0, strokeWeight : 1, zIndex : 1 };
        }
        c.path = [a, b];

        poly = new google.maps.Polyline(c);

        return poly;
    }

    /*
     * path - int [] - Indices of vertecies along the path
     * options? - object - Options to pass to Polyline contructor.
     */
    this._paintPath = function(path, options) {
        var latLngArray = new google.maps.MVCArray();
        var vertex;

        for (var i = 0; i < path.length; ++i) {
            vertex = _currentSolution.Graph.Vertices[path[i]];
            latLngArray.push(new google.maps.LatLng(vertex.Latitude, vertex.Longitude));
        }

        options.path = latLngArray;

        return this._paintPolyline2(options);
    }

    this._addMarker = function(lat, lng) {
        var marker = new google.maps.Marker( {
            position : new google.maps.LatLng(lat, lng),
            flat : true,
            icon : "http://www.google.com/mapmaker/mapfiles/red-truffle.png"
        } );

        _markers.push(marker);

        return marker;
    }

    this.addTest = function() {
        _output.Tests.push({ Graph : { Vertices : _vertices, Edges : _edges } });
    }

    this.addGridMarkers = function(columns, rows) {
        var marker;
        this.setVertex(false);
        _markers = [];
        _vertices = [];
        this.setEdge(false);
        _edgePolys = [];
        _edges = [];

        var width = (columns > 47 ? columns : 47);
        var height = (rows > 19 ? rows : 19);
        var latStart = 29;
        var lonStart = -122;
        var lonSpacing = width / columns;
        var latSpacing = height / rows;

        for (var i = 0; i < columns; ++i) {
            for (var j = 0; j < rows; ++j) {
                marker = this._addMarker(latStart + (j * latSpacing), lonStart + (i * lonSpacing));
                _vertices.push({ Latitude : marker.getPosition().lat(), Longitude : marker.getPosition().lng() });
            }
        }
    }

    this.addRandomMarkers = function(num) {
        var marker;
        this.setVertex(false);
        _markers = [];
        _vertices = [];
        this.setEdge(false);
        _edgePolys = [];
        _edges = [];

        for (var i = 0; i < num; ++i) {
            marker = this._addMarker((Math.random() * 100) % 19 + 29, (Math.random() * 1000) % 47 - 122);

            _vertices.push({ Latitude : marker.getPosition().lat(), Longitude : marker.getPosition().lng() });
        }
    }

    /*
     * rate - Number - 1-10 - density of edges.  10 is complete.  1 is very sparse.
     */
    this.setRandomEdges = function(rate) {
        this.setEdge(false);
        _edgePolys = [];
        _edges = [];

        for (var i = 0; i < _markers.length - 1; ++i) {
            for (var j = i + 1; j < _markers.length; ++j) {
                if (parseInt(Math.random() * 10) < rate) {
                    _edges.push([i, j]);
                    _edgePolys.push(this._paintPolyline(_markers[i].getPosition(), _markers[j].getPosition()));
                }
            }
        }
    }

    /*
     * 69 miles/degree
     */
    this.setNearbyEdges = function(radius, rate) {
        this.setEdge(false);
        _edgePolys = [];
        _edges = [];

        for (var i = 0; i < _markers.length - 1; ++i) {
            for (var j = i + 1; j < _markers.length; ++j) {
                if (Math.sqrt(Math.pow(_markers[i].getPosition().lat() - _markers[j].getPosition().lat(), 2) + Math.pow(_markers[i].getPosition().lng() - _markers[j].getPosition().lng(), 2)) * 69 < radius && parseInt(Math.random() * 10) < rate) {
                    _edges.push([i, j]);
                    _edgePolys.push(this._paintPolyline(_markers[i].getPosition(), _markers[j].getPosition()));
                }
            }
        }
    }

    this.setSolutions = function(solutions) {
        _solutions = solutions;
        return _solutions.Results.length;
    }

    this.setSolution = function(index) {
        var self = this;
        this.reset();
        _currentSolution = _solutions.Results[index];

        for (var i = 0; i < _currentSolution.Graph.Vertices.length; ++i) {
            var marker = this._addMarker(_currentSolution.Graph.Vertices[i].Latitude, _currentSolution.Graph.Vertices[i].Longitude);
            marker.Index = i;
            google.maps.event.addListener(marker, 'click', function(event) {
                self.getShortestPath(this.Index);
            });
        }

        for (var i = 0; i < _currentSolution.Graph.Edges.length; ++i) {
            var edge = _currentSolution.Graph.Edges[i];
            _edgePolys.push(
                this._paintPolyline(
                    new google.maps.LatLng(_currentSolution.Graph.Vertices[edge[0]].Latitude, _currentSolution.Graph.Vertices[edge[0]].Longitude),
                    new google.maps.LatLng(_currentSolution.Graph.Vertices[edge[1]].Latitude, _currentSolution.Graph.Vertices[edge[1]].Longitude)
                )
            );
        }

        var index = 0;
        do {
            _convexHullPolys.push(
                this._paintPolyline(
                    new google.maps.LatLng(_currentSolution.Graph.Vertices[_currentSolution.ConvexHull[index]].Latitude, _currentSolution.Graph.Vertices[_currentSolution.ConvexHull[index]].Longitude),
                    new google.maps.LatLng(_currentSolution.Graph.Vertices[_currentSolution.ConvexHull[index + 1]].Latitude, _currentSolution.Graph.Vertices[_currentSolution.ConvexHull[index + 1]].Longitude),
                    { strokeColor : "#FF00FF", strokeOpacity : 0.5, strokeWeight : 10, zIndex : 2 }
                )
            );
        } while (++index < _currentSolution.ConvexHull.length - 1);

        for (var i = 0; i < _currentSolution.MinimumCostSpanningTree.length; ++i) {
            _minimumSpanningPolys.push(
                this._paintPolyline(
                    new google.maps.LatLng(_currentSolution.Graph.Vertices[_currentSolution.MinimumCostSpanningTree[i][0]].Latitude, _currentSolution.Graph.Vertices[_currentSolution.MinimumCostSpanningTree[i][0]].Longitude),
                    new google.maps.LatLng(_currentSolution.Graph.Vertices[_currentSolution.MinimumCostSpanningTree[i][1]].Latitude, _currentSolution.Graph.Vertices[_currentSolution.MinimumCostSpanningTree[i][1]].Longitude),
                    { strokeColor : "#00FF00", strokeOpacity : 0.5, strokeWeight : 10, zIndex : 2 }
                )
            );
        }
    }

    this._setCurrentShortestPath = function() {
        if (_shortestPathPoly !== null) {
            this.setShortestPath(false);
            _shortestPathPoly = null;
        }
        _shortestPathPoly = this._paintPath(_currentSolution.ShortestPaths[_shortestPathCurrent], { strokeColor : "#0000FF", strokeOpacity : 0.5, strokeWeight : 10, zIndex : 2 });
        this.setShortestPath(true);
        _onNewShortestPath({ Number : _shortestPathCurrent + 1 });
    }

    this.play = function() {
        var self = this;
        _shortestPathCurrent = 0;

        if (!_shortestPathRunnning) {
            _shortestPathRunnning = true;
            var run = function() {
                if (_shortestPathRunnning && _shortestPathCurrent < _currentSolution.ShortestPaths.length) {
                    self._setCurrentShortestPath();
                    ++_shortestPathCurrent;
                    setTimeout(run, _shortestPathRate);
                } else {
                    self.stop();
                    self.setShortestPath(false);
                    _shortestPathPoly = null;
                }
            }

            setTimeout(run, 0);
        }
    }

    this.stop = function() {
        _shortestPathRunnning = false;
    }

    this.next = function() {
        this.stop();
        if (++_shortestPathCurrent == _currentSolution.ShortestPaths.length) {
            --_shortestPathCurrent;
        }
        this._setCurrentShortestPath();
    }

    this.previous = function() {
        this.stop();
        if (--_shortestPathCurrent < 0) {
            ++_shortestPathCurrent;
        }
        this._setCurrentShortestPath();
    }

    this.first = function() {
        this.stop();
        _shortestPathCurrent = 0;
        this._setCurrentShortestPath();
    }

    this.last = function() {
        this.stop();
        _shortestPathCurrent = _currentSolution.ShortestPaths.length - 1;
        this._setCurrentShortestPath();
    }

    this.slowForward = function() {
        _shortestPathRate *= 2;
    }

    this.fastForward = function() {
        _shortestPathRate /= 2;
    }

    this.isConnected = function() {
        return _currentSolution.Connected;
    }

    /*
     * a - index to a vertex
     * b? - index to a vertex
     * TODO: behavior
     */
    this.getShortestPath = function(a, b) {
        if (b === undefined) {
            if (_shortestPathFrom === undefined) {
                _shortestPathFrom = a;
            } else if (_shortestPathTo === undefined) {
                _shortestPathTo = a;
            } else {
                _shortestPathFrom = _shortestPathTo;
                _shortestPathTo = a;
            }
        } else {
            _shortestPathFrom = a;
            _shortestPathTo = b;
        }

        if (_shortestPathFrom !== undefined && _shortestPathTo !== undefined) {
            this.setShortestPath(false);
            _shortestPathPoly = null;

            for (var i = 0; i < _currentSolution.ShortestPaths.length; ++i) {
                var path = _currentSolution.ShortestPaths[i];
                if ((path[0] === _shortestPathFrom && path[path.length - 1] === _shortestPathTo) || (path[0] === _shortestPathTo && path[path.length - 1] === _shortestPathFrom)) {
                    _shortestPathPoly = this._paintPath(_currentSolution.ShortestPaths[i], { strokeColor : "#0000FF", strokeOpacity : 0.5, strokeWeight : 10, zIndex : 2 });
                    break;
                }
            }
            this.setShortestPath(true);
        }
    }

    /* show - boolean - true -> paint vertex markers, false -> remove vertex markers */
    this.setVertex = function(show) {
        for (var i = 0; i < _markers.length; ++i) {
            _markers[i].setMap((show ? _map : null));
        }
    }

    /* show - boolean - true -> paint edge polys, false -> remove edge polys */
    this.setEdge = function(show) {
        for (var i = 0; i < _edgePolys.length; ++i) {
            _edgePolys[i].setMap((show ? _map : null));
        }
    }

    /* show - boolean - true -> paint hull polys, false -> remove hull polys */
    this.setConvexHull = function(show) {
        for (var i = 0; i < _convexHullPolys.length; ++i) {
            _convexHullPolys[i].setMap((show ? _map : null));
        }
    }

    /* show - boolean - true -> paint min span polys, false -> remove min span polys */
    this.setMinimumSpanning = function(show) {
        for (var i = 0; i < _minimumSpanningPolys.length; ++i) {
            _minimumSpanningPolys[i].setMap((show ? _map : null));
        }
    }

    /* show - boolean - true -> paint shortest path polys, false -> remove shortest path polys */
    this.setShortestPath = function(show) {
        if (_shortestPathPoly !== null) {
            _shortestPathPoly.setMap((show ? _map : null));
        }
    }

    this.getConvexHull = function(sol) {
        for (var i = 0; i < sol.Results.length; ++i) {
            sol.Results[i].ConvexHull = [];

            var leftMost = sol.Results[i].Graph.Vertices.length;
            var next;
            var minVal = 181;

            for (var j = 0; j < sol.Results[i].Graph.Vertices.length; ++j) {
                if (sol.Results[i].Graph.Vertices[j].Longitude < minVal) {
                    minVal = sol.Results[i].Graph.Vertices[j].Longitude;
                    leftMost = j;
                }
            }

            next = leftMost;

            var previousPoint = { Longitude : sol.Results[i].Graph.Vertices[leftMost].Longitude, Latitude : 0 };
            var currentPoint;  //this will be leftmost point here
            var tempPoint;  //used to test the next possible hull point

            do {
                sol.Results[i].ConvexHull.push(next);
                var maxAngle = -1;
                currentPoint = sol.Results[i].Graph.Vertices[next];

                for (var j = 0; j < sol.Results[i].Graph.Vertices.length; ++j) {
                    if (next == j) { continue; }

                    tempPoint = sol.Results[i].Graph.Vertices[j];
                    
                    var tempAngle = Math.acos(
                        (
	                        (Math.pow(currentPoint.Longitude - tempPoint.Longitude, 2) + Math.pow(currentPoint.Latitude - tempPoint.Latitude, 2)) +
	                        (Math.pow(currentPoint.Longitude - previousPoint.Longitude, 2) + Math.pow(currentPoint.Latitude - previousPoint.Latitude, 2)) -
	                        (Math.pow(previousPoint.Longitude - tempPoint.Longitude, 2) + Math.pow(previousPoint.Latitude - tempPoint.Latitude, 2))
                        )
                        /
                        (
	                        2 * 
	                        Math.sqrt(Math.pow(currentPoint.Longitude - tempPoint.Longitude, 2) + Math.pow(currentPoint.Latitude - tempPoint.Latitude, 2)) *
	                        Math.sqrt(Math.pow(currentPoint.Longitude - previousPoint.Longitude, 2) + Math.pow(currentPoint.Latitude - previousPoint.Latitude, 2))
                        )
                    );

                    if (tempAngle > maxAngle) {
                        next = j;
                        maxAngle = tempAngle;
                    }
                }

                previousPoint = currentPoint;
            } while (next !== leftMost);

            sol.Results[i].ConvexHull.push(leftMost);
        }
    }

    /*
     * http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf  Problem 1
     * I think Dijkstra's algorithm is bogus, so I made up my own* (after reading the wiki on Prim's algorithm).
     * todo: minimum cost spanning tree
     */
    this.getMinimumSpanningTree = function(sol) {
        for (var i = 0; i < sol.Results.length; ++i) {
            var I = [];
            var II = [];
            var III = [];
            var A = [];
            var B = [];
            //var arbitraryNode = 0;
            var N = 0;


            //Intualize A with an arbitrary node.
            A.push(N);
            //Initualize B with remainder of nodes.
            for (var j = 1; j < sol.Results[i].Graph.Vertices.length; ++j) {
                B.push(j);
            }
            //Initualize III with all edges
            for (var j = 0; j < sol.Results[i].Graph.Edges.length; ++j) {
                III.push(sol.Results[i].Graph.Edges[j]);
            }

            do {
                //Move verticies in III to II where N is an endpoint and the other endpoint is in B
                for (var j = 0; j < B.length; ++j) {
                    var tempIII = [];
                    for (var k = 0; k < III.length; ++k) {
                        if ((III[k][0] === N && III[k][1] === B[j]) || (III[k][1] === N && III[k][0] === B[j])) {
                            II.push(III[k]);
                        } else {
                            tempIII.push(III[k]);
                        }
                    }
                    III = tempIII;
                }

                //Set minEdge to the minimum cost edge in II.
                var minLength = 403;  //402.5 is max length on earth in degrees.
                var minEdge = undefined
                for (var j = 0; j < II.length; ++j) {
                    var n1 = sol.Results[i].Graph.Vertices[II[j][0]];
                    var n2 = sol.Results[i].Graph.Vertices[II[j][1]];
                    var length = Math.sqrt(Math.pow(n1.Longitude - n2.Longitude, 2) + Math.pow(n1.Latitude - n2.Latitude, 2));
                    if (length < minLength) {
                        minLength = length;
                        minEdge = II[j];
                        //Set N to the endpoint of E that does not exist in A.
                        N = (A.some(function(element, index, array) { return element === II[j][0]; }) ? II[j][1] : II[j][0]);
                    }
                }
                
                //Move minEdge from II to I.
                I.push(minEdge);
                var tempII = [];
                for (var j = 0; j < II.length; ++j) {
                    if (II[j] !== minEdge) {
                        tempII.push(II[j]);
                    }
                }
                II = tempII;
                
                //Move N from A to B.
                A.push(N);
                var tempB = [];
                for (var j = 0; j < B.length; ++j) {
                    if (B[j] !== N) {
                        tempB.push(B[j]);
                    }
                }
                B = tempB;
                
                //todo:  edges from II where both nodes are in A
                var tempII = [];
                for (var j = 0; j < II.length; ++j) {
                    if (A.some(function(element, index, array) { return element === II[j][0]; }) &&
                        A.some(function(element, index, array) { return element === II[j][1]; })) {
                        III.push(II[j]);
                    } else {
                        tempII.push(II[j]);
                    }
                }
                II = tempII;

            } while (B.length > 0);

            sol.Results[i].MinimumCostSpanningTree = I;
        }

    }

    /*
     * http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
     * todo: shortest paths
     * trick: have to have two edges for undirected graphs [A, B] and [B, A]
     */
    this.getAllPairsShortestPaths = function(sol) {
        for (var i = 0; i < sol.Results.length; ++i) {
            sol.Results[i].ShortestPaths = [];

            var doubleEdges = [];
            for (j = 0; j < sol.Results[i].Graph.Edges.length; ++j) {
                var temp = [sol.Results[i].Graph.Edges[j][1], sol.Results[i].Graph.Edges[j][0]];
                doubleEdges.push(sol.Results[i].Graph.Edges[j]);
                doubleEdges.push(temp);
            }

            for (var source = 0; source < sol.Results[i].Graph.Vertices.length; ++source) {
                var vertices = [];

                //Step 1
                for (j = 0; j < sol.Results[i].Graph.Vertices.length; ++j) {
                    vertices.push( { index : j, predecessor : null, distance : (j === source ? 0 : Infinity) } );
                }

                //Step 2
                for (var j = 0; j < vertices.length - 1; ++j) {
                    for (var k = 0; k < doubleEdges.length; ++k) {
                        var uv = doubleEdges[k];
                        var u = vertices[uv[0]];
                        var v = vertices[uv[1]];
                        var length = Math.sqrt(Math.pow(sol.Results[i].Graph.Vertices[uv[0]].Longitude - sol.Results[i].Graph.Vertices[uv[1]].Longitude, 2) + Math.pow(sol.Results[i].Graph.Vertices[uv[0]].Latitude - sol.Results[i].Graph.Vertices[uv[1]].Latitude, 2));
                        if (u.distance + length < v.distance) {
                            v.distance = u.distance + length;
                            v.predecessor = u.index
                        }
                    }
                }

                for (var j = 0; j < vertices.length; ++j) {
                    if (j === source) {
                        continue;
                    }
                    var arraystring = "";
                    var currentstart = j;
                    do {
                        var predo = vertices[currentstart].predecessor;
                        arraystring = currentstart + ',' + arraystring;
                        currentstart = predo;
                    } while (predo !== null);
                    arraystring = arraystring.substr(0, arraystring.length - 1);
                    var shortestPath = arraystring.split(',');
                    for (var k = 0; k < shortestPath.length; ++k) {
                        shortestPath[k] = parseInt(shortestPath[k]);
                    }
                    sol.Results[i].ShortestPaths.push(shortestPath);
                }
            }
        }

    }

    /*
     * returns JSON string that can be input as a solution
     */
    this.getTestSolutions = function() {
        var sol = { Results : [] };

        //copy original graphs
        for (var i = 0; i < _output.Tests.length; ++i) {
            sol.Results.push(_output.Tests[i]);
        }

        //todo: is connected
        for (var i = 0; i < sol.Results.length; ++i) {
            sol.Results[i].Connected = true;
        }

        this.getConvexHull(sol);
        this.getMinimumSpanningTree(sol);
        this.getAllPairsShortestPaths(sol);

        return JSON.stringify(sol);
    }

    this.reset = function() {
        _output = { Tests : [] };
        _currentSolution = null;
        
        /* remove poly & marker paintings  */
        this.setVertex(false);
        this.setEdge(false);
        this.setConvexHull(false);
        this.setMinimumSpanning(false);
        this.setShortestPath(false);

        /* remove poly & marker objects */
        _vertices = [];
        _markers = [];
        _edgePolys = [];
        _convexHullPolys = [];
        _minimumSpanningPolys = [];
        _shortestPathPoly = null;
        
        /* remove state */
        _shortestPathFrom = _shortestPathTo = undefined;
        _shortestPathCurrent = null
        _shortestPathRunnning = false;
    }
}


var thing;

function initialize() {
    thing = new tgd.Tools.MapGraph(
        document.getElementById("map_canvas"),
        function(args) {
            tgd.Tools.MapGraph.GUI.Menu.Labels.CurrentPath.textContent = args.Number;
        }
    );

    tgd.Tools.MapGraph.GUI = {
        Menu : {
            Labels : {
                Solution : document.getElementById("lblSolution"),
                Create : document.getElementById("lblCreate"),
                Connected : document.getElementById("lblConnected"),
                CurrentPath : document.getElementById("lblCurrentMinimumPath"),
                TotalPaths : document.getElementById("lblTotalMinimumPaths"),
                PathsRate : document.getElementById("lblMinimumPathsRate")
            },
            Panels : {
                Solution : document.getElementById("panSolution"),
                Create : document.getElementById("panCreate")
            },
            TextAreas : {
                Solution : document.getElementById("txtSolution"),
                Output : document.getElementById("txtOutput")
            },
            DropDownLists : {
                Solution : document.getElementById("ddlSolution")
            },
            CheckBoxes : {
                Vertices : document.getElementById("cbVertex"),
                ConvexHull : document.getElementById("cbConvexHull"),
                MinimumSpanning : document.getElementById("cbMinimumSpanning"),
                Edges : document.getElementById("cbEdge")
            },
            TextBoxes : {
                NumColumns : document.getElementById("txtNumColumns"),
                NumRows : document.getElementById("txtNumRows")
            }
        }
    };
}

function submitSolution() {
    try {
        var solutions = JSON.parse(tgd.Tools.MapGraph.GUI.Menu.TextAreas.Solution.value)
    } catch (e) {
        alert('Solution is not formatted correctly.');
        return;
    }

    var numSolutions = thing.setSolutions(solutions);

    setSolutionOptions(numSolutions);
}

function setSolution(index) {
    thing.setSolution(index);
    tgd.Tools.MapGraph.GUI.Menu.Labels.TotalPaths.textContent = thing.NumShortestPaths;
    tgd.Tools.MapGraph.GUI.Menu.Labels.Connected.textContent = thing.isConnected();
    setSwitches();
}

function setSolutionOptions(num) {
    for (var i = tgd.Tools.MapGraph.GUI.Menu.DropDownLists.Solution.length - 1; i > 0; --i) {
        tgd.Tools.MapGraph.GUI.Menu.DropDownLists.Solution.remove(i);
    }

    for (var i = 0; i < num; ++i) {
        var option = document.createElement("option");
        option.label = option.text = "Solution #" + i;
        option.value = i;
        tgd.Tools.MapGraph.GUI.Menu.DropDownLists.Solution.appendChild(option);
    }
}

function setSwitches() {
    thing.setVertex(tgd.Tools.MapGraph.GUI.Menu.CheckBoxes.Vertices.checked);
    thing.setEdge(tgd.Tools.MapGraph.GUI.Menu.CheckBoxes.Edges.checked);
    thing.setConvexHull(tgd.Tools.MapGraph.GUI.Menu.CheckBoxes.ConvexHull.checked);
    thing.setMinimumSpanning(tgd.Tools.MapGraph.GUI.Menu.CheckBoxes.MinimumSpanning.checked);
}

        //]]>
            </script>
            <style type="text/css">
                html{height:100%}
                body{height:100%;margin:0;padding:0;}
                #map_canvas{height:100%;}

                #menu{position:absolute;z-index:1;margin:10px;color:#000;font-size:10pt;}
                .menuButton{background:#ccc;border:solid 1px #aaa;border-bottom:none;padding:5px;}
                .menuButton.current{background:#fff;border-color:#249;border-bottom:solid 1px #fff;}
                .menuBox{background:#fff;border:solid 1px #249;margin-top:5px;padding:10px;position:absolute;z-index:-1;}
                .menuBox div{white-space:nowrap;margin:10px 0;}
                #menu fieldset{text-align:center;}
                #menu fieldset span.button{border:solid 1px #ccc;padding:5px;}
                #menu fieldset span.button:hover{background:#ccc;}

                .hidden{display:none;}
                input[type="button"]{border:solid 1px #ccc;background:#aaa;color:#fff;font-family:consolas,monospace;font-size:1em;}
                input[type="text"],textarea,select{background:#ccc;border:solid 1px #aaa;color:#000;font-family:consolas,monospace;font-size:1em;}
                textarea{width:100%;}
                .button,label{cursor:pointer;}
            </style>
        </head>
        <body onload="initialize()">
            <div id="menu">
                <span id="lblSolution" class="menuButton" onclick="tgd.Tools.MapGraph.GUI.Menu.Labels.Create.depress();tgd.Tools.MapGraph.GUI.Menu.Panels.Create.hide();this.press();tgd.Tools.MapGraph.GUI.Menu.Panels.Solution.show();">Solution</span>
                <div id="panSolution" class="menuBox hidden">
                    <div>
                        <select id="ddlSolution" onchange="if (parseInt(this.value) >= 0) { setSolution(parseInt(this.value)); }">
                            <option value="-1">Choose a Solution</option>
                        </select>
                    </div>
                    <fieldset>
                        <legend>
                            Elements to Show
                        </legend>
                        <div>
                            <label for="cbVertex">Vertices</label>
                            <input type="checkbox" id="cbVertex" onchange="thing.setVertex(this.checked);" />
                        </div>
                        <div>
                            <label for="cbEdge">Edges</label>
                            <input type="checkbox" id="cbEdge" onchange="thing.setEdge(this.checked);" />
                        </div>
                        <div>
                            <label for="cbConvexHull">Convex Hull</label>
                            <input type="checkbox" id="cbConvexHull" onchange="thing.setConvexHull(this.checked);" />
                        </div>
                        <div>
                            <label for="cbMinimumSpanning">Minimum Spanning Tree</label>
                            <input type="checkbox" id="cbMinimumSpanning" onchange="thing.setMinimumSpanning(this.checked);" />
                        </div>
                    </fieldset>
                    <fieldset>
                        <legend>
                            Shortest Paths
                        </legend>
                        <div>
                            <span class="button" title="first" onclick="thing.first();">|&lt;</span>
                            <span class="button" title="slow forward" onclick="thing.slowForward();tgd.Tools.MapGraph.GUI.Menu.Labels.PathsRate.textContent = thing.ShortestPathRate;">&lt;&lt;</span>
                            <span class="button" title="previous" onclick="thing.previous();">&lt;</span>
                            <span class="button" title="play" onclick="thing.play();">|&gt;</span>
                            <span class="button" title="next" onclick="thing.next();">&gt;</span>
                            <span class="button" title="stop" onclick="thing.stop();">[]</span>
                            <span class="button" title="fast forward" onclick="thing.fastForward();tgd.Tools.MapGraph.GUI.Menu.Labels.PathsRate.textContent = thing.ShortestPathRate;">&gt;&gt;</span>
                            <span class="button" title="last" onclick="thing.last();">&gt;|</span>
                        </div>
                        <div>
                            <span id="lblCurrentMinimumPath">0</span>
                            of
                            <span id="lblTotalMinimumPaths">#</span>
                        </div>
                        <div>
                            Rate:
                            <span id="lblMinimumPathsRate">0</span>
                        </div>
                </fieldset>
                <div>
                    <input type="button" value="Shortest Paths" />
                </div>
                <div>
                    Connected?
                    <span id="lblConnected"></span>
                </div>
                <div>
                    <textarea id="txtSolution" rows="10"></textarea>
                </div>
                <div>
                    <input type="button" onclick="submitSolution();" value="Submit" />
                    <input type="button" value="Cancel" onclick="tgd.Tools.MapGraph.GUI.Menu.Labels.Solution.depress();tgd.Tools.MapGraph.GUI.Menu.Panels.Solution.hide();" />
                </div>
            </div>
            <span id="lblCreate" class="menuButton" onclick="tgd.Tools.MapGraph.GUI.Menu.Labels.Solution.depress();tgd.Tools.MapGraph.GUI.Menu.Panels.Solution.hide();this.press();tgd.Tools.MapGraph.GUI.Menu.Panels.Create.show();">Create</span>
            <div id="panCreate" class="menuBox hidden">
                <div>
                    <label for="txtNumVerticies"># verticies</label>
                    <input id="txtNumVerticies" type="text" size="4" maxlength="4" />
                    <input type="button" onclick="thing.addRandomMarkers(parseInt(document.getElementById('txtNumVerticies').value));thing.setVertex(true);" value="Add Vertices" />
                </div>
                <div>
                    <label for="txtNumColumns"># columns</label>
                    <input id="txtNumColumns" type="text" size="2" maxlength="2" />
                    <label for="txtNumRows"># rows</label>
                    <input id="txtNumRows" type="text" size="2" maxlength="2" />
                    <input type="button" onclick="thing.addGridMarkers(parseInt(tgd.Tools.MapGraph.GUI.Menu.TextBoxes.NumColumns.value), parseInt(tgd.Tools.MapGraph.GUI.Menu.TextBoxes.NumRows.value));thing.setVertex(true);" value="Add Vertices" />
                </div>
                <div>
                    <label for="txtEdgeRate1">Edge Rate [1-10]</label>
                    <input id="txtEdgeRate1" type="text" size="2" maxlength="2" />
                    <input type="button" onclick="thing.setRandomEdges(parseInt(document.getElementById('txtEdgeRate1').value));thing.setEdge(true);" value="Random Edges" />
                </div>
                <div>
                    <label for="txtEdgeRate2">Edge Rate [1-10]</label>
                    <input id="txtEdgeRate2" type="text" size="2" maxlength="2" />
                    <label for="txtRadius">Radius (miles)</label>
                    <input id="txtRadius" type="text" size="4" maxlength="4" />
                    <input type="button" onclick="thing.setNearbyEdges(parseInt(document.getElementById('txtRadius').value), parseInt(document.getElementById('txtEdgeRate2').value));thing.setEdge(true);" value="Nearby Edges" />
                </div>
                <div>
                    <input type="button" onclick="thing.addTest();tgd.Tools.MapGraph.GUI.Menu.TextAreas.Output.value = thing.Output;" value="Add Test" />
                    <input type="button" onclick="thing.reset();" value="Reset" />
                </div>
                <div>
                    <textarea id="txtOutput" readonly="readonly" rows="10" width="100%" onfocus="this.select();"></textarea>
                </div>
                <div>
                    <input type="button" value="Cancel" onclick="tgd.Tools.MapGraph.GUI.Menu.Labels.Create.depress();tgd.Tools.MapGraph.GUI.Menu.Panels.Create.hide();" />
                    <input type="button" value="Solutions" onclick="tgd.Tools.MapGraph.GUI.Menu.TextAreas.Solution.textContent = thing.getTestSolutions();submitSolution();setSolution(0);" />
                </div>
            </div>
        </div>
        <div id="map_canvas"></div>
    </body>
</html>
